package July;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author:gao
 * @date:2020/7/9
 * @time:8:08
 * @version:0.0.1
 * @description:none
 */


//面试题 17.13. 恢复空格
public class ReSpace {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.respace(new String[]{"potimzz"}
        ,"potimzzpotimzz");
    }
}


//dp 处理边界条件版
class Solution001 {
    public int respace(String[] dictionary, String sentence) {
        if(sentence==null||sentence.length()==0)return 0;
        int LENGTH = sentence.length();
        int[] dp = new int[LENGTH]; //表示到i有多少未识别德（包括i）
        dp[0] = 1;
        for (String str : dictionary) {
            if (str.equals("" + sentence.charAt(0))) {
                dp[0] = 0;
                break;
            }
        }
        for (int i = 1; i < LENGTH; i++) {
            dp[i] = dp[i - 1] + 1;
            for (String str : dictionary) {
                if(i+1-str.length()>0
                        &&str.equals(sentence.substring(i+1-str.length(),i+1))){
                    dp[i]=Math.min(dp[i],dp[i-str.length()]);
                }else if(i+1-str.length()==0
                        &&str.equals(sentence.substring(i+1-str.length(),i+1))){
                    dp[i]=0;
                }
            }
        }
        return dp[LENGTH-1];
    }
}

//dp 多申请一个空间
class Solution002 {
    public int respace(String[] dictionary, String sentence) {
        if(sentence==null||sentence.length()==0)return 0;
        int LENGTH = sentence.length();
        int[] dp = new int[LENGTH+1]; //表示到i前有多少未识别德（不包括i）
        for (int i = 0; i <LENGTH ; i++) {
            dp[i+1]=dp[i]+1;
            for (String str:dictionary){
                if (i+1-str.length()>=0
                        &&str.equals(sentence.substring(i+1-str.length(),i+1))) {
                    dp[i+1]=Math.min(dp[i+1],dp[i+1-str.length()]);
                }
            }
        }
        return dp[LENGTH];
    }
}



//使用字典树进行优化
class Trie{
    private Trie[] next;
    private boolean isEnd; //用于判断是否存在一个比当前串短的字串
    //构造方法
    public Trie(){
        next = new Trie[26];
        isEnd=false;
    }
    public Trie getNext(int index){
        return next[index];
    }

    //判断是否到头了
    public boolean hasNext(int index){
        return this.next[index]!=null;
    }
    public boolean hasThisSubStr(){
        return isEnd;
    }
    //倒序构造一颗树
    public void insert(String s){
        Trie cur = this;
        for (int i = s.length()-1; i >=0 ; i--) {
            int index = s.charAt(i)-'a';
            if(!cur.hasNext(index)) cur.next[index]= new Trie();
            cur = cur.next[index];
        }
        cur.isEnd =true;
    }
}

class Solution {
    public int respace(String[] dictionary, String sentence) {
        int LEN = sentence.length();
        int[] dp = new int[LEN+1]; //记录i前的，不包括i
        Trie root = new Trie();
        for (String s: dictionary){
            root.insert(s);
        }
        for (int i = 0; i <sentence.length() ; i++) {
            dp[i+1]=dp[i]+1;
            Trie cur = root;
            for (int j = i; j >=0 ; j--) {
                //字典树，先用判断是否存在当前字符，走到那个字符，
                // 在判断是否有以它结尾的字串
                int index = sentence.charAt(j)-'a';
                if(cur.hasNext(index)) cur = cur.getNext(index);
                else break;
                if(cur.hasThisSubStr()){
                    dp[i+1] = Math.min(dp[i+1],dp[j]);
                }
            }
        }
        return dp[LEN];
    }
}